// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

type TreeNode struct {
	Data  int
	Left  *TreeNode
	Right *TreeNode
}

func deepestLeavesSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var queue = make([]*TreeNode, 0)
	queue = append(queue, root)
	var curSum int
	for len(queue) > 0 {
		var sz = len(queue)
		curSum = 0
		for i := 0; i < sz; i++ {
			curSum += queue[i].Data
			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
			}
		}
		queue = queue[sz:]
	}
	return curSum
}

func main() {
	root := &TreeNode{1, nil, nil}
	node2 := &TreeNode{2, nil, nil}
	node3 := &TreeNode{3, nil, nil}
	node4 := &TreeNode{4, nil, nil}
	node5 := &TreeNode{5, nil, nil}
	node6 := &TreeNode{6, nil, nil}
	root.Left = node2
	root.Right = node3
	node2.Left = node4
	node2.Right = node5
	node3.Right = node6
	res := deepestLeavesSum(root)
	fmt.Println(res)
}

//$ go run interview5-7.go
//15
